/*
 * @lc app=leetcode.cn id=1203 lang=cpp
 *
 * [1203] 项目管理
 *
 * https://leetcode.cn/problems/sort-items-by-groups-respecting-dependencies/description/
 *
 * algorithms
 * Hard (61.52%)
 * Likes:    203
 * Dislikes: 0
 * Total Accepted:    13.2K
 * Total Submissions: 21.4K
 * Testcase Example:  '8\n2\n[-1,-1,1,0,0,1,0,-1]\n[[],[6],[5],[6],[3,6],[],[],[]]'
 *
 * 有 n 个项目，每个项目或者不属于任何小组，或者属于 m 个小组之一。group[i] 表示第 i 个项目所属的小组，如果第 i
 * 个项目不属于任何小组，则 group[i] 等于 -1。项目和小组都是从零开始编号的。可能存在小组不负责任何项目，即没有任何项目属于这个小组。
 * 
 * 请你帮忙按要求安排这些项目的进度，并返回排序后的项目列表：
 * 
 * 
 * 同一小组的项目，排序后在列表中彼此相邻。
 * 项目之间存在一定的依赖关系，我们用一个列表 beforeItems 来表示，其中 beforeItems[i] 表示在进行第 i 个项目前（位于第 i
 * 个项目左侧）应该完成的所有项目。
 * 
 * 
 * 如果存在多个解决方案，只需要返回其中任意一个即可。如果没有合适的解决方案，就请返回一个 空列表 。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 
 * 
 * 输入：n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems =
 * [[],[6],[5],[6],[3,6],[],[],[]]
 * 输出：[6,3,4,1,5,2,0,7]
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems =
 * [[],[6],[5],[6],[3],[],[4],[]]
 * 输出：[]
 * 解释：与示例 1 大致相同，但是在排序后的列表中，4 必须放在 6 的前面。
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 1 
 * group.length == beforeItems.length == n
 * -1 
 * 0 
 * 0 
 * i != beforeItems[i][j]
 * beforeItems[i] 不含重复元素
 * 
 * 
 */

// @lc code=start
class Solution {
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        vector<int> res;
        vector<int> ind(n); // 入度
        vector<vector<int>> outd(n); // 后置项目
        vector<int> gind(m); // 统计小组的入度
        for (int i = 0; i < n; ++i) {
            ind[i] = beforeItems[i].size();
            for (int j : beforeItems[i]) {
                outd[j].emplace_back(i);
                if (group[j] != group[i] && group[i] > -1) {
                    ++gind[group[i]];
                }
            }
        }

        vector<vector<int>> g(m + 1); // 保存该小组的当前入度为 0 的项目, g[i] 表示第 i - 1 对应的项目
        for (int i = 0; i < n; ++i) {
            if (ind[i] == 0) {
                g[group[i] + 1].emplace_back(i); 
            }
        }

        queue<int> que;
        for (int i = 0; i < m; ++i) {
            if (gind[i] == 0) {
                que.emplace(i);
            }
        }

        auto topo = [&](int i) {
            while (!g[i + 1].empty()) {
                int t = g[i + 1].back();
                g[i + 1].pop_back();
                res.emplace_back(t);
                for (auto j : outd[t]) {
                    --ind[j];
                    if (ind[j] == 0) {
                        g[group[j] + 1].emplace_back(j);
                    }
                    if (group[j] > -1 && group[j] != i) {
                        --gind[group[j]];
                        if (gind[group[j]] == 0) {
                            que.emplace(group[j]);
                        }
                    }
                }
            }
        };

        while (!que.empty() || !g[0].empty()) {
            topo(-1);
            while (!que.empty()) {
                int i = que.front();
                que.pop();
                topo(i);
            }            
        }

        return res.size() == n ? res : vector<int>({});        
    }
};
// @lc code=end

